package sit.engreal.leetcode.problems100;

import org.junit.jupiter.api.Assertions;
import sit.engreal.leetcode.util.ListNode;

/**
 * <a href="https://leetcode.cn/problems/remove-nth-node-from-end-of-list/">19. 删除链表的倒数第 N 个结点</a>
 */
public class LeetCode19 {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode q = head;
        while (--n > 0 && q != null) {
            q = q.next;
        }
        if (q == null) {
            return head;
        }
        if (q.next == null) {
            return head.next;
        }

        ListNode p = head;
        while (q.next.next != null) {
            p = p.next;
            q = q.next;
        }
        p.next = p.next.next;
        return head;
    }

    public static void main(String[] args) {
        final LeetCode19 demo = new LeetCode19();

        {
            final ListNode head = ListNode.array2list(new int[]{1, 2, 3, 4, 5});
            final ListNode output = demo.removeNthFromEnd(head, 6);

            Assertions.assertArrayEquals(
                    new int[]{1, 2, 3, 4, 5},
                    ListNode.list2array(output));
        }

        {
            final ListNode head = ListNode.array2list(new int[]{1, 2, 3, 4, 5});
            final ListNode output = demo.removeNthFromEnd(head, 2);

            Assertions.assertArrayEquals(
                    new int[]{1, 2, 3, 5},
                    ListNode.list2array(output));
        }

        {
            final ListNode head = ListNode.array2list(new int[]{1, 2, 3, 4, 5});
            final ListNode output = demo.removeNthFromEnd(head, 4);

            Assertions.assertArrayEquals(
                    new int[]{1, 3, 4, 5},
                    ListNode.list2array(output));
        }

        {
            final ListNode head = ListNode.array2list(new int[]{1});
            final ListNode output = demo.removeNthFromEnd(head, 1);

            Assertions.assertArrayEquals(
                    new int[]{},
                    ListNode.list2array(output));
        }
    }
}
